package com.leecode.xiehf.page_02;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
 * https://leetcode-cn.com/problems/spiral-matrix/
 */
public class Solution_0054 {

    public static void main(String[] args) {
        Solution_0054 solution = new Solution_0054();
        int[][] n = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };
        List<Integer> s = solution.spiralOrder(n);
        s.forEach(ss -> {
            System.out.println(ss + ",");
        });
    }

    public List<Integer> spiralOrder(int[][] matrix) {

        // 维度最长，缺口用null输出
        int max_ver = matrix.length;
        int max_hor = 0;
        for (int[] ints : matrix) {
            if (ints.length > max_hor) {
                max_hor = ints.length;
            }
        }
        // 如果第二维没有元素，就不需要处理了。
        if (max_hor == 0) {
            return new ArrayList<>();
        }
        List<Integer> integers = new ArrayList<>();
        horizontal(integers, matrix, true, 0, 0, max_hor, max_ver);
        return integers;
    }

    /**
     * 水平方向
     *
     * @param integers 输出结果
     * @param matrix   二位数组
     * @param positive 方向
     *                 true 左往右
     *                 false 从右往左
     * @param startX   开始的横坐标
     * @param startY   开始的纵坐标
     * @param maxHor   水平最大长度
     * @param marVer   垂直最大长度
     */
    private void horizontal(List<Integer> integers, int[][] matrix, boolean positive, int startX, int startY, int maxHor, int marVer) {
        if (maxHor == 0) {
            return;
        }
        if (positive) {
            int end = startX + maxHor;
            for (int i = startX; i < end; i++) {
                int num = matrix[startY][i];
                integers.add(num);
            }
            vertical(integers, matrix, true, end - 1, startY + 1, maxHor, marVer - 1);
        } else {
            int end = startX - maxHor;
            for (int i = startX; i > end; i--) {
                int num = matrix[startY][i];
                integers.add(num);
            }
            vertical(integers, matrix, false, end + 1, startY - 1, maxHor, marVer - 1);
        }
    }

    /**
     * 垂直方向
     *
     * @param integers
     * @param matrix
     * @param positive 方向
     *                 true 从上往下
     *                 false 从下往上
     * @param maxHor   水平最大长度
     * @param marVer   垂直最大长度
     */
    private void vertical(List<Integer> integers, int[][] matrix, boolean positive, int startX, int startY, int maxHor, int marVer) {
        if (marVer == 0) {
            return;
        }
        if (positive) {
            int end = startY + marVer;
            for (int i = startY; i < end; i++) {
                int num = matrix[i][startX];
                integers.add(num);
            }
            horizontal(integers, matrix, false, startX - 1, end - 1, maxHor - 1, marVer);
        } else {
            int end = startY - marVer;
            for (int i = startY; i > end; i--) {
                int num = matrix[i][startX];
                integers.add(num);
            }
            horizontal(integers, matrix, true, startX + 1, end + 1, maxHor - 1, marVer);
        }
    }
}
